/*
 * Algorytm Forda-Fulkersona do rozwiazania problemu transportowego
 * 
 * Wg procedury TRANSPORT z ksiazki: 
 * "Algorytmy optymalizacji dyskretnej z programami w jezyku pascal"
 * Maciej M. Syslo, Narsingh Deo, Janusz S. Kowalik
 * 
 */
package protrans;

/**
 *
 * @author suchezi
 * @param tablica jedno-wymiarowa konsumentow
 * @param tablica jedno-wymiarowa producentow
 * @param tablica dwu-wymiarowa kosztow transportu
 * 
 */
public class Algorytm {
    /*
     * jak inaczej zapisac nieskonczonosc ?
     * 
     * Juz wszystko piknie dziala  :D
     * 
     */
    
    private int inf = Integer.MAX_VALUE;
    private int kroki, ko;
    private int[] producenci;    //= {15, 30, 55};
    private int[] konsumenci;    //= {30, 10, 15, 45};
    private int[][] koszty;
//    private int[][] koszty = {
//        {3, 7, 3, 4},
//        {5, 7, 2, 6},
//        {8, 13, 9, 4}
//    };
    private int[][] x;           //= new int[producenci.length][konsumenci.length];
    
    String getWynik() {
        String blee = new String();
        Integer xx = new Integer(0);
        for(int p=0; p < producenci.length; p++) {
            for(int k=0; k < konsumenci.length; k++) {
                xx = x[p][k];
                blee += Integer.toString(xx) + " ";
            }
            blee += "\n";
        }
        return blee;
    }

    Algorytm(int[] prod, int[] kons, int[][] koszt) {
        producenci = prod;
        konsumenci = kons;
        koszty = koszt;
        x = new int[producenci.length][konsumenci.length];
        
        int[] u = new int[producenci.length];
        int[] v = new int[konsumenci.length];
        // poczatkowy wektor v
        int r = inf;
        int i, j, ra, sf;
        for (i=0; i < producenci.length; i++) {
            for (j=0; j < konsumenci.length; j++) {
                sf = koszty[i][j];
                if (sf < r) {
                    r = sf;
                }
            }
            v[i] = r;
        }
        // ------------------------------
        boolean lab, lab2;
        boolean lab1 = false;
        int[] w = new int[producenci.length];
        int[] eps = new int[producenci.length];
        int[] k = new int[konsumenci.length];
        int[] del = new int[konsumenci.length];
        do {
            for (i = 0; i < producenci.length; i++) {
                w[i] = -1;
                eps[i] = producenci[i];
            }
            for (j = 0; j < konsumenci.length; j++) {
                k[j] = -1;
                del[j] = 0;
            }
            do {
                i = 0;
                lab = lab2 = true;
                do {
                    sf = eps[i];
                    eps[i] = -eps[i];
                    if (sf > 0) {
                        ra = u[i];
                        j = 0;
                        do {
                            if ((del[j] == 0) && (v[j] - ra == koszty[i][j])) {
                                k[j] = i;
                                del[j] = sf;
                                lab = false;
                                if (konsumenci[j] > 0) {
                                    lab = true;
                                    lab2 = false;
                                    sf = Math.abs(del[j]);
                                    r = konsumenci[j];
                                    if (r < sf) {
                                        sf = r;
                                    }
                                    konsumenci[j] = r - sf;
                                    do {
                                        i = k[j];
                                        x[i][j] += sf;
                                        j = w[i];
                                        if (j != -1) {
                                            x[i][j] -= sf;
                                        }
                                    } while (j != -1);
                                    producenci[i] -= sf;

                                    // if b[j] <= 0 for all j, OPTIMAL
                                    j = 0;
                                    do {
                                        lab1 = (konsumenci[j] <= 0);
                                        j++;
                                    } while ((j < konsumenci.length) && (lab1));
                                    if (lab1) {
                                        ko = 0;
                                        for (i = 0; i < producenci.length; i++) {
                                            for (j = 0; j < konsumenci.length; j++) {
                                                ko += x[i][j] * koszty[i][j];
                                            }
                                        }
                                    }
                                }
                            }
                            j++;
                        } while ((j < konsumenci.length) && (lab2));
                    }
                    i++;
                } while ((i < producenci.length) && (lab2));
                if (!lab) {
                    lab = true;
                    for (j = 0; j < konsumenci.length; j++) {
                        sf = del[j];
                        if (sf > 0) {
                            for (i = 0; i < producenci.length; i++) {
                                if (eps[i] == 0) {
                                    r = x[i][j];
                                    if (r > 0) {
                                        w[i] = j;
                                        if (r <= sf) {
                                            eps[i] = r;
                                        } else {
                                            eps[i] = sf;
                                        }
                                        lab = false;
                                    }
                                }
                            }
                            del[j] = -sf;
                        }
                    }
                }
            } while (!lab);

            if (lab2) {
                r = inf;
                for (i = 0; i < producenci.length; i++) {
                    if (eps[i] != 0) {
                        ra = u[i];
                        for (j = 0; j < konsumenci.length; j++) {
                            if (del[j] == 0) {
                                sf = koszty[i][j] + ra - v[j];
                                if (r > sf) {
                                    r = sf;
                                }
                            }
                        }
                    }
                }
                for (i = 0; i < producenci.length; i++) {
                    if (eps[i] == 0) {
                        u[i] += r;
                    }
                }
                for (j = 0; j < konsumenci.length; j++) {
                    if (del[j] == 0) {
                        v[j] += r;
                    }
                }
            }
            kroki++;
            if (kroki == 10000) {
                System.exit(kroki);
            }
        } while (!lab1);
    }
}
